package com.it.base.arithmetic.map;



/**
 *  实现mymap来定义具体的实现
 *  hashmap使用的是数组+链表+红黑树来实现
 *  本例子中使用数组+链表的简单实现，红黑色后面在进行修改
 *
 */
public class CustomMap<K,V>  {
    ///位桶数组,bucket
    private Entry[] table;
    private int size;
    //kv键值对
    private   class Entry<K,V> {
        //
        int hash;
        //key
         K key;
        //value
         V val;
        Entry<K, V> next;

    }

    /**
     * 构造方法，通过构造方法初始化位桶数组大小，默认16
     */
    public CustomMap() {
        this.table =new Entry[16];
    }

    /**
     * 首先有一个put方法
     */
    public void put(K key,V val){
        //先生成一个节点
        Entry entry = new Entry();
        //计算当前节点需要在落到数组的下标位置
        entry.hash=myHash(key.hashCode(),table.length);
        entry.key=key;
        entry.val=val;
        //查看当前数组下标上是否有值，没有值就直接存在当前下标就可以
        Entry tmp = table[entry.hash];
        //  如果当前数据下标没有值，则直接写入即可
        if(tmp==null){
            table[entry.hash] = entry;
            size++;
        }else {
        //如果当前节点有值，需要遍历链表，
            while (tmp!=null){
                //如果key相同的，则覆盖原来key的val,这也是hashmap为什么加入相同key，值会覆盖的原因
                 if(tmp.key.equals(key)){
                     tmp.val=val;
                     //数据处理完毕，需要跳出
                     break;
                 }else {
                     if(tmp.next==null){
                        tmp.next=entry;
                        size++;
                        break;
                     }else{
                         //指针指向下一个节点
                         tmp=tmp.next;
                     }
                 }
            }

        }
    }
    //假设table中是有值的
    public V getValue(K key){
        int hash= myHash(key.hashCode(),table.length);
        V val=null;
        if(table[hash]!=null){
            Entry tmp = table[hash];
            while (tmp!=null){
                    if(tmp.key.equals(key)){
                        val=(V) tmp.val;
                        break;
                    }else {
                        tmp=tmp.next;
                    }

            }
        }
        return val;

    }
    //通过取余方式来看当前节点应该落在那个数组的下标上
    //取余数，不会发生数组下标越界，实际上在hashmap源码中，使用了比这个效率更加高效的位运算
    private int myHash(int vCode,int length){
        return vCode % length;
    }

    public static void main(String[] args) {
        CustomMap customMap = new CustomMap();
        customMap.put("a","a");
        customMap.put("b","b");
        customMap.put("c","c");
        customMap.put("d","d");
        System.out.printf((String) customMap.getValue("a"));

    }
}